I. Field of the Invention
The present invention relates to communications. More particularly, the present invention relates to a method for decoding with partial state information on a convolutionally encoded channel.
II. Description of the Related Art
The use of code division multiple access (CDMA) modulation techniques is one of several techniques for facilitating communications in which a large number of system users are present. Although other techniques such as time division multiple access (TDMA), frequency division multiple access (FDMA), and AM modulation schemes such as amplitude companded single sideband (ACSSB) are known, CDMA has significant advantages over these other techniques. The use of CDMA techniques in a multiple access communication system is disclosed in U.S. Pat. No. 4,901,307, entitled xe2x80x9cSPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS,xe2x80x9d and assigned to the assignee of the present invention and incorporated by reference herein. The use of CDMA techniques in a multiple access communication system is further disclosed in U.S. Pat. No. 5,103,459, entitled xe2x80x9cSYSTEM AND METHOD FOR GENERATING SIGNAL WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEMxe2x80x9d, assigned to the assignee of the present invention and incorporated by reference herein. The CDMA system can be designed to conform to the xe2x80x9cTIA/EIA/IS-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular Systemxe2x80x9d, hereinafter referred to as the IS-95 standard. Another code division multiple access communication system includes the GLOBALSTAR communication system for world wide communication utilizing low earth orbiting satellites.
In accordance with the IS-95 standard, a paging channel is used to transmit paging messages from the base station to the remote stations. The paging messages can be broadcast messages directed toward all remote stations or specific messages directed at a particular remote station. Paging messages can be used to alert the remote station of a pending communication with the base station or to transmit small amounts of data.
For wireless communication systems, such as the CDMA, TDMA, and GLOBALSTAR systems, slotted mode paging is utilized to minimize battery power consumption and improve standby time. For slotted mode paging, each remote station is assigned paging slots which can be selected in accordance with the phone number of the remote station. To conserve battery power, many functional blocks within the remote station are turned off or placed in the sleep mode for the duration between the assigned slots. Prior to the start of the assigned slots, the remote station is activated. In the awake mode, the remote station initializes the functional blocks to prepare for demodulation and decoding of the assigned slot for paging messages.
In accordance with IS-95 standard, the paging channel is convolutionally encoded to provide forward error correction capability. A rate 1/N convolutional encoder encodes each input bit into N code symbols called a code branch in accordance with a set of N generator polynomials. Each generator polynomial G(x) computes one code symbol. The N code symbols are combined into an N-bit code branch. Since each input bit is encoded into N code symbols, the code rate for the convolutional encoder is 1/N.
The constraint length K of the encoder is the number of data bits used in the encoding process and determines the error correcting capability of the code. Long constraint length K yields improved performance at the expense of hardware and computational complexity. A state in the convolutional encoder is designated by the K-1 prior input bits into the encoder. For a constraint length K encoder, there are 2K-1 possible states. For each of the 2K-1 states, a xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99 input bit results in one of two possible code branches.
Typically, a Viterbi decoder is used to decode the transmitted code branches at the receiver. A discussion on the theory and operation of the Viterbi decoder is contained in the paper xe2x80x9cConvolutional Codes and Their Performance in Communication Systemsxe2x80x9d by A. Viterbi, IEEE Transaction on Communication Technology, Vol. COM19, no. 5, October 1971, pgs. 821-835. Under certain assumptions about the channel noise, the Viterbi decoder performs the maximum likelihood decoding of the transmitted data sequence. For each received N code symbols, the branch metric of all branches entering each state is computed and added to the corresponding prior path metrics. The best path entering each state is selected and stored as the new path metrics. The path metric is also referred to as the state metric in the art. The selected path is stored in a path memory. In xe2x80x9cDevelopment of Variable Rate Viterbi Decoder and Its Performance Characteristics,xe2x80x9d Sixth International Conference on Digital Satellite Communications, Phoenix, Ariz., September 1983, Y. Yasuda et al. show that the survivor paths with the best path metric all converge to the same path after a certain chain back depth. Thus, a Viterbi decoded bit is obtained by tracing a path back by at least the chain back distance.
In accordance with IS-95 standard, the paging channel is convolutionally encoded with a rate xc2xd, constraint length K=9 convolutional encoder. However, unlike the forward traffic channel, the convolutional encoder for the paging channel is not flushed with K-1 code tail bits at the end of each 20 msec frame. Therefore, at the remote station, the Viterbi decoder is not able to reset to a known state at the start of each frame. Instead, the Viterbi decoder is operated for a predetermined amount of time prior to the start of the assigned slot to allow convergence of the decoding trellis. The duration of time the remote station is activated prior to the assigned slot represents a waste of battery power which shortens the standby time of the remote station.
The present invention is a novel and improved method for decoding a convolutionally encoded channel with partial state information. In the present invention, the certainties of transmitted bits at predetermined locations in time can be ascertained a priori. This information is then used to set the states of a Viterbi decoder to different state metrics in accordance with the certainties of the transmitted bits. High certainty of a transmitted bit results in resetting the states corresponding to that bit to a very good state metric. In contrast, low certainty of a transmitted bit results in resetting the states corresponding to that bit to a very bad state metric. Resetting the states to different state metrics improves the decoding performance and shortens the time required to converge the decoding trellis by eliminating improbable paths.
The present invention is especially applicable to a CDMA paging channel wherein slotted mode paging is used and each receiving remote station is assigned paging slots which are spaced apart in time. In the exemplary embodiment, there is a high probability that the M bits immediately prior to the start of the assigned slots are known a priori. In the exemplary IS-95 system, these bits can be zero padding bits. In fact, the IS-95 system can be operated to ensure that the M bits immediately prior to the start of the assigned slots are zero padding bits. This information is used to reset the states within the Viterbi decoder accordingly. The improved decoding performance as the result of the partial state reset includes shortened initialization time and lower probability of decoding error.
It is an object of the present invention to improve decoding performance by utilizing a priori knowledge that the four bits immediately prior to the assigned slot are very likely or most definitely known. For the exemplary IS-95 system, the high probability or absolute certainty that these four bits are padding bits result from the unique structure of the paging channel message capsule, as defined by IS-95 standard or by system design, respectively. This information is used to reset states 0 through 15 within Viterbi decoder to the best or a very good state metric and states 16 through 255 to the worst or a very bad state metric. By eliminating over 93 percent of possible states from consideration, the decoding performance is improved.
It is another object of the present invention to improve decoding performance by utilizing a priori knowledge that the three bits immediately prior to the assigned slot have a high probability of being zero padding bits. This certainty is ascertained by the unique structure of the paging channel message capsule as specified by IS-95 standard. This information is used to reset states 0 through 31 within Viterbi decoder to the best or a very good state metric and states 32 through 255 to the worst or a very bad state metric. By eliminating over 87 percent of possible states from consideration, the decoding performance is improved.
It is yet another object of the present invention to improve decoding performance by utilizing a priori knowledge that the transmitted bits closest to the assigned slot have increasing probability of being zero padding bits. Again, this certainty is ascertained by the unique structure of the paging channel message capsule as specified by IS-95 standard. This information is used to reset states 0 through 7 within Viterbi decoder to the best state metric, states 8 through 15 to a very good metric, states 16 through 31 to a good metric, states 32 through 63 to a medium metric, states 64 through 127 to a very bad metric, and states 128 through 255 to the worst state metric. By resetting the states to a range of state metrics in accordance with the certainties of the bits being zero padding bits, improved decoding performance is obtained.